package com.github.hgkmail.hello.leetcode101.dp.oned;

import java.util.Arrays;

//典型的一维dp，子问题是以nums[i]结尾的数组
//dp[i]= Math.max(nums[i], nums[i]+dp[i-1])，加上前面的能变大则加，否则不加
public class LC53MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        if (len<=0) {
            return 0;
        }
        int[] dp=new int[len];
        for (int i = 0; i < len; i++) {
            if (i==0) {
                dp[i]=nums[i];
                continue;
            }
            dp[i]= Math.max(nums[i], nums[i]+dp[i-1]);
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(new LC53MaximumSubarray().maxSubArray(new int[]{5,4,-1,7,8}));
    }
}

